#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int minCost(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	int dx[5]= { 0, 0, 0, 1, -1 },dy[5]= { 0, 1, -1, 0, 0 };
	const int INF = 0x3f3f3f3f;
	vector<vector<int>> dis(m,vector<int>(n, INF));
	dis[0][0] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
	heap.push({ 0,0 });
	while (!heap.empty())
	{
		auto [distance, node] = heap.top();
		heap.pop();
		int x1 = node / n, y1 = node % n;
		if (distance > dis[x1][y1])
			continue;
		for (int k = 1; k <= 4; k++)
		{
			int x2 = x1 + dx[k], y2 = y1 + dy[k];
			if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n)
			{
				int tmp = distance + (grid[x1][y1] == k ? 0 : 1);
				if (tmp < dis[x2][y2])
				{
					dis[x2][y2] = tmp;
					heap.push({ dis[x2][y2], x2 * n + y2 });
				}
			}
		}
	}
	return dis[m-1][n-1];
}
int minimumObstacles(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
	const int INF = 0x3f3f3f3f;
	vector<vector<int>> dis(m, vector<int>(n, INF));
	vector<vector<bool>> visited(m, vector<bool>(n, false));
	dis[0][0] = 0;
	visited[0][0] = true;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
	heap.push({ 0,0 });
	while (!heap.empty())
	{
		auto [distance, node] = heap.top();
		heap.pop();
		int x = node / n, y = node % n;
		if (visited[x][y] == true)
			continue;
		visited[x][y] = true;
		for (int k = 0; k < 4; k++)
		{
			int x1 = x + dx[k], y1 = y + dy[k];
			if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n)
			{
				int tmp = distance + (grid[x1][y1] == 1 ? 1 : 0);
				if (tmp < dis[x1][y1])
				{
					dis[x1][y1] = tmp;
					heap.push({ dis[x1][y1],x1 * n + y1 });
				}
			}
		}
	}
	return dis[m - 1][n - 1];
}
int main()
{
	vector<vector<int>> grid = { {0,1,1},{1,1,0},{1,1,0} };
	minimumObstacles(grid);
	return 0;
}